687. 最长同值路径

Similar Question

124. 二叉树中的最大路径和 - 力扣（LeetCode）

Solution Tips

方案一: 模拟 + 递归

var longestUnivaluePath = function(node) {
    // 看起来就是普通的遍历一下, 然后记录最长的相同值的 node 就可以了
    // 先后序遍历均可

    // 不行, 不是单纯的先后序遍历可以处理的, 想象一下从最左侧的节点到最右侧节点的最长路径
    // 经典的左和右? 左侧的最长 + 右侧的最长, 还是不行, 会漏掉 path
    // 想要遍历一个二叉树所有的边, 必须通过一次先序+后序

    // 遍历所有的边, 按理说是和遍历所有的节点相同的, 所以没必要模拟题意
    // 就看单个节点, 左节点和右节点是否与自己相同, 如果相同就标记 +1, 再递归
    let max = 0;
    recursion(node);
    return max;

    function recursion(node) {
        if (node === null) return 0;

        let leftLen = 0;
        let rightLen = 0;
        if (node.left) {
            if (node.val === node.left.val) {
                leftLen += recursion(node.left) + 1;
            }
            else {
                recursion(node.left);
            }
        }

        if (node.right) {
            if (node.val === node.right.val) {
                rightLen += recursion(node.right) + 1;
            }
            else {
                recursion(node.right);
            }
        }

        // 自己视角的路径是 左 + 右 + 自己
        max = Math.max(max, leftLen + rightLen);
        // 但是能向上传递的就只能是左右里最长的那一条
        return Math.max(leftLen, rightLen);
    }

};

console.log(longestUnivaluePath(t.root))